package shujujiegou;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import org.junit.Test;


public class Sort {
	
	private static int maxSize = 1000000;
	
	//��������
	public static void main(String[] args) {
		int amount = 10000000;
		int start = 0;
		int end = 11111111;
		int size = end - start +1; 
		Random r = new Random();
		StringBuilder[] scount = null;
		if(size <= maxSize){
//			List<String> list = new ArrayList<String>();
//			for(int i=0;i<size;i++){
//				list.add("0");
//			}
			scount = new StringBuilder[size];
			for(int i=0;i<size;i++){
				scount[i] = new StringBuilder("0");
			}
			for(int i=0;i<amount;i++){
				int rnum = r.nextInt(size);
				int intCount = Integer.valueOf(scount[rnum].toString());
				scount[rnum].replace(0, scount[rnum].length(), String.valueOf(++intCount));
			}
			System.out.println();
		} else {
			scount = new StringBuilder[maxSize];
//			StringBuilder initString = new StringBuilder();
//			for(int i=0;i < size/maxSize;i++){
//				initString.append("0/");
//			}
			for(int i=0;i<maxSize;i++){
				scount[i] = new StringBuilder("");
			}
			//
			for(int i=0;i<amount;i++){
				System.out.println(i);
				int rnum = r.nextInt(size);
				//��rnum����maxsizeʱ 
				//rnum/maxsize��ʾ���ַ����еڼ�������   stringindex ��1��ʼ
				//rnum%maxsize��ʾ�ַ���������±�  index
				int stringindex = rnum / maxSize + 1;
				int index = rnum % maxSize;
//				System.out.println(scount[index]+"  "+scount[index].split("/").length+" "+stringindex);
				if(scount[index].toString().split("/").length-1<stringindex){
					StringBuilder initString = new StringBuilder();
					for(int j=0;j < stringindex;j++){
						initString.append("/0");
					}
					scount[index] = initString;
				}
				
				String tmpString = scount[index].toString();
				//�ҵ���stringindex������   Ȼ���һ
				int beginIndex = getCharacterPosition2(tmpString, "/", stringindex);
				int endIndex = getCharacterPosition2(tmpString, "/", stringindex+1);
				String snum = null;
//				System.out.println(beginIndex+"---"+endIndex);
				if(endIndex == -1){
					snum = tmpString.substring(beginIndex+1);
					int inum = Integer.valueOf(snum);
					scount[index].replace(beginIndex+1, scount[index].length(), String.valueOf(++inum));
				}else{
					snum = tmpString.substring(beginIndex+1, endIndex);
					int inum = Integer.valueOf(snum);
					scount[index].replace(beginIndex+1, endIndex, String.valueOf(++inum));
				}
			}
			
			System.out.println();
			
			
		}
		
		
		
		
		

		
	}
	//��ȡ�ַ����е�i�γ��ֵ��ַ�λ�� 
	private static int getCharacterPosition(String string,String reg, int i) {
		Matcher m = Pattern.compile(reg).matcher(string);
	    int mIdx = 0;
	    while(m.find()) {
	       mIdx++;
	       //��"/"���ŵ�i�γ��ֵ�λ��
	       if(mIdx == i){
	    	   return m.start();
	       }
	      
	    }
	    
		return -1;
	}

	//��ȡ�ַ����е�i�γ��ֵ��ַ�λ�� 
	private static int getCharacterPosition2(String string,String reg, int i) {
		char creg = 0;
		if(reg.length()==1){
			creg = reg.charAt(0);
		}else{
			creg = reg.charAt(0);
			//TODO
		}
		if(i<1){
			return -1;
		}
		
		int findcount = 0;
		for(int j=0;j<string.length();j++){
			if(string.charAt(j) == creg){
				findcount++;
			}
			if(findcount==i){
				return j;
			}
		}
		
		return -1;
	}
	@Test
	public void test(){
		String s = "";
		for(int i=0;i<10;i++){
			s+="2131/";
		}
		
		long t = System.currentTimeMillis();
		int i = getCharacterPosition2(s,"/",3);
		System.out.println(System.currentTimeMillis()-t);
		long tt = System.currentTimeMillis();
		int j = getCharacterPosition(s, "/", 3);
		System.out.println(System.currentTimeMillis()-tt);
	}
	
	
	
	
	
}
